package uestc.lj.basic.tree;

import uestc.lj.leetcode.day1.Solution;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断一棵树是否是完全二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code06_IsCST {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
	public static boolean isCST(Node head) {
		if (head == null) {
			return true;
		}

		Queue<Node> queue = new LinkedList<>();
		//是否遇到左右两个孩子不双全的节点
		boolean leaf = false;
		Node leftChild = null;
		Node rightchild = null;
		queue.add(head);
		while (!queue.isEmpty()) {
			head = queue.poll();
			leftChild = head.left;
			rightchild = head.right;
			if ((leaf && (leftChild != null || rightchild != null)) || (leftChild == null && rightchild != null)) {
				return false;
			}
			if (leftChild != null) {
				queue.add(leftChild);
			}
			if (rightchild != null) {
				queue.add(rightchild);
			}
			if (leftChild == null || rightchild == null) {
				leaf = true;
			}
		}
		return true;
	}
	public boolean isCompleteTree(TreeNode root) {
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		boolean reachNull = false;
		q.add(root);
		while(!q.isEmpty()){
			TreeNode t = q.poll();
			if(t == null){
				reachNull = true;
			}
			if(t != null){
				if(reachNull) {
					return false;
				}
				q.add(t.left);
				q.add(t.right);
			}
		}
		return true;
	}
}
